package com.yc.bestMatching;


public class EditDistance {
    /***
     * 计算word1变为word2要编辑几次  =》 编辑距离
     * @param word1
     * @param word2
     * @return
     */
    public static int calculate(String word1,String word2) {
        //初始一个矩阵 以保存两个单词之间的距离
        int[][] distances = new int[word1.length() + 1][word2.length() + 1];

        //初始化 第一列
        for (int i = 1; i <= word1.length(); i++) {
            distances[i][0] = i;
        }
        //初始化第一行
        for (int j = 1; j <= word2.length(); j++) {
            distances[0][j] = j;
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                //如果字符串中的第 i 个字符和第 j 个字符不相等 将编辑距离设为左上角未知的值加1 否则 保持不变
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    //相等 所以将左上角的值做为[i][j]的值
                    distances[i][j] = distances[i - 1][j - 1];
                } else {
                    //不相等 则从[i][j]位置左 左上 上 三个位置的值中取最小值  这个最小值加1 填充到[i][j]位置
                    // [i-1][j] 上边代表删除  [i][j-1] 左边代表插入字符  [i-1][j-1]左上代表替换字符
                    distances[i][j] = minimum(distances[i - 1][j], distances[i][j - 1], distances[i - 1][j - 1]) + 1;
                }
            }
        }
        return distances[word1.length()][word2.length()];
    }

    private static int minimum(int i,int j,int k){
        return Math.min(i,Math.min(j,k));
    }
}
